Problem statement: zenit15kkk

Kleofáš a postupnosť

Počet bodov: 40, časový limit: 1000ms

Kleofáš má na papieri napísanú nejakú postupnosť čísel. Ako bývalému veľkému biznismenovi sa mu však páčia iba rastúce postupnosti čísel. Preto sa rozhodol, že niektoré čísla zo svojej postupnosti vyškrtne tak, aby nevyšktrnuté čísla tvorili rastúcu postupnosť. Navyše má Kleofáš rád, keď sú čísla veľké. Preto chce čísla vyškrtať tak, aby súčet nevyškrtnutých čísel bol najväčší možný (pri tom stále musia tvoriť rastúcu postupnosť).

Úloha

Na vstupe dostanete postupnosť \(n\) čísel. Nájdite najväčší možný súčet postupnosti, ktorú môžete dostať vyškrtaním niekoľkých prvkov vstupnej postupnosti a ktorá je navyše rastúca. Vzniknutá postupnosť môže byť aj prázdna, vtedy je jej súčet nula.

Vstup a výstup

V prvom riadku vstupu je jedno celé číslo \(n\) (\(1 \leq n \leq 100\, 000\)). V druhom riadku je \(n\) medzerou oddelených čísel z rozsahu \(-10^9\) až \(10^9\) – čísla postupnosti v poradí, v akom sú napísané na papieri.

Vypíšte jeden riadok obsahujúci jedno celé číslo: najväčší súčet, ktorý môže Kleofáš dostať.

Ak vaše riešenie zvládne vyriešiť všetky vstupy, kde \(n \leq 1000\), dostane aspoň polovicu bodov.

Príklady

Input:

12
-8 3 10 5 4 19 10 12 -2 20 20 30

Output:

82

Najväčší súčet dostaneme, ak nám po vyškrtaní ostane postupnosť 3 10 19 20 30. Postupnosti -8 3 10 19 20 30, aj 3 5 10 12 20 30 sú síce dlhšie, ale majú menší súčet.

Input:

5
-1 -1 -1 -1 -1

Output:

0

V tomto prípade sa Kleofášovi oplatí vyškrtnúť všetko, čím dostane prázdnu postupnosť so súčtom nula.